package leetcode100

// TODO 动态规划 【-】 乘积最大子数组
// TODO https://leetcode.cn/problems/maximum-product-subarray/solution/by-wwsw-frc3/

func maxProduct(nums []int) int {
	prevMin, prevMax, maxRes := nums[0], nums[0], nums[0]
	for i := 1; i < len(nums); i++ {
		tmp1 := prevMin * nums[i]
		tmp2 := prevMax * nums[i]
		prevMin = min6(min6(tmp1, tmp2), nums[i]) // 维护：三者之min，因为若prevMin为负数&&nums[i]为负数，乘积可能是最大的
		prevMax = max6(max6(tmp1, tmp2), nums[i]) // 维护：三者之max
		maxRes = max6(maxRes, prevMax)            // 取max
	}
	return maxRes
}

func min6(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max6(a, b int) int {
	if a > b {
		return a
	}
	return b
}
